/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/palindrome-partitioning
   @Language: C++
   @Datetime: 16-02-09 08:20
   */

class Solution {
	bool ispalindrome(const string &s,int start,int end){
		for(--end; start<end;)
			if (s[start++]!=s[end--])
				return false;
		return true;
	}
	void partcore(string &s,int pos
			,vector<vector<string> > &vvs,vector<string> &vs){
		if (pos>=s.length()){
			vvs.push_back(vs);
			return;
		}
		for(int i=pos; i<s.length(); ++i){
			if (!ispalindrome(s,pos,i+1)) continue;
			vs.push_back(s.substr(pos,i-pos+1));
			partcore(s,i+1,vvs,vs);
			vs.pop_back();
		}
	}

public:
	/**
	 * @param s: A string
	 * @return: A list of lists of string
	 */
	vector<vector<string> > partition(string s) {
		// write your code here
		vector<vector<string> > vvs;
		vector<string> vs;
		partcore(s,0,vvs,vs);
		return vvs;
	}
};
